package String.easy;

/**
 * 1.问题描述
 *      给定两个由小写字母构成的字符串 A 和 B ，只要我们可以通过交换 A 中的两个字母得到与 B 相等的结果，
 *      就返回 true ；否则返回 false 。
 *
 *      交换字母的定义是取两个下标 i 和 j （下标从 0 开始），只要 i!=j 就交换 A[i] 和 A[j] 处的字符。
 *      例如，在 "abcd" 中交换下标 0 和下标 2 的元素可以生成 "cbad" 。
 *
 *      理解题意：
 *          当字符串A中仅仅交换两个字符之后可以和B相等，则称A，B为亲密字符，如果A中超过两个位置的字符与B不相同
 *          则A，B一定不是亲密字符串
 *
 *      对于亲密字符串而言，只有两种情况，要么是亲密的，要么是非亲密的
 *
 * 2.算法分析
 *      1.暴力穷举法
 *          首先我们考虑一个长为n的字符串有多少种交换方式(每次交换该字符串中的两个字符)一共有n(n-1)/2
 *          种可能性
 *
 *          时间复杂度已经超过了leetcode平台的时间限额，没有通过，所以此方法并不可行，除非比较的字符串的长度较小
 *          可以直接使用暴力穷举的方式来解决此题
 *
 *          换一种思路
 *
 *      算法分析：
 *          首先我们从题意出发，假设给定两个字符串A，B，如果A的长度不等于B的，此时一定不是亲密字符串
 *          所以下面的所有考虑都是在A，B字符串的长度相同的情况下讨论
 *
 *          假设对于A[i]和B[i]而言，只有两种情况：1.A[i] == B[i]，此时A的第i个字符与B的第i个字符是匹配的
 *          2.A[i] != B[i],此时不匹配，如果此时A[i]与A[j]交换之后，A与B相等，此时我们可以推出A[i]=B[j]
 *          A[j]=B[i],整个问题围绕着A[i],A[j],B[i],B[j]着四个数来分析
 *
 *          从整体上分析，我们将上述分成两种情况讨论：
 *              1. A == B (此时A与B为相同的字符串)
 *                  此时说明A[i] = B[i] i = 0,1,2,...,n 假设长度为n的字符串
 *                  由上述的局部的分析，我们知道如果字符串中的字符都是单字符，即每个字符只出现了一次
 *                  则一定不能通过交换之后匹配，但是一旦出现一个字符出现的次数大于等于2，此时就一定可
 *                  以交换之后匹配
 *
 *                  具体的例子：
 *                      1.A = "aab"  B = "aab"
 *                      2.A = "ab"   B = "ab" 显然不能通过交换ab来匹配
 *
 *              2. A != B (此时A与B为不同的字符串)
 *                  对于不同的字符串，我们需要找到两个不匹配的两个索引，之后在进行比较
 *                  设置两个整形变量来记录发生不匹配的两个索引
 *
 * 3.代码实现
 */
@SuppressWarnings("all")
public class 亲密字符串 {
    public static void main(String[] args) {
        // 交换A的头尾或者B的头尾即可，所以返回true
        String A = "aab";
        String B = "aba";
        //System.out.println(swapString(A, 0, 1));
        System.out.println(test1(A,B));
    }

    // 算法实现1：暴力穷举法
    public static boolean buddyStrings(String A, String B) {
        // 判断边界
        if (A == null || B == null || A.length() != B.length()) {
            return false;
        }
        for (int i = 0; i < A.length(); i ++) {
            for (int j = i+1;j < A.length(); j++) {
                String s = swapString(A, i, j);
                if (s.equals(B)) {
                    return true;
                }
                swapString(A,i,j); // 还原
            }
        }
        return false;
    }

    /**
     * 交换字符串指定位置的字符，并返回交换之后的字符串
     * @param target
     * @param i
     * @param j
     * @return
     */
    public static String swapString(String target,int i ,int j) {
        if (i < 0 || i > target.length() || j < 0 || j > target.length()) {
            return "";
        }
        char[] charArray = target.toCharArray();
        charArray[i] = target.charAt(j);
        charArray[j] = target.charAt(i);
        StringBuilder builder = new StringBuilder();
        for (char c : charArray) {
            builder.append(c);
        }
        return builder.toString();
    }

    public static boolean test(String A,String B) {
        if(A == null || B == null || A.length() != B.length() || A.equals(B)) {
            return false;
        }
        int[] arrA = new int[26];
        int[] arrB = new int[26];
        for (int i = 0; i < A.length(); i++) {
            arrB[B.charAt(i) - 'a'] += 1;
            arrA[A.charAt(i) - 'a'] += 1;
        }
        for (int i = 0; i < arrA.length; i++) {
            if (arrA[i] != arrB[i]) {
                    return false;
            }
        }
        return true;
    }


    /**
     * 正确的答案
     * @param A
     * @param B
     * @return
     */
    public static boolean test1(String A,String B) {
        if (A.length() != B.length()) return false;
        // 当A和B为相同字符串的时候
        if (A.equals(B)) {
            int[] count = new int[26];
            for (int i = 0; i < A.length(); ++i)
                count[A.charAt(i) - 'a']++;

            for (int c: count)
                if (c > 1) return true; // 有字符出现的次数大于等于2
            return false; // 此时每个字符出现的次数为1，此时一定为false
        } else {
            // 找到发生不匹配的索引
            int first = -1, second = -1;
            for (int i = 0; i < A.length(); ++i) {
                if (A.charAt(i) != B.charAt(i)) {
                    if (first == -1)
                        first = i;
                    else if (second == -1)
                        second = i;
                    else
                        /*
                            为什么此时会直接返回false？
                            当我们找到第一对不匹配的索引first和second时，此时两者的值均不为-1，但是第一次找到的时候
                            不会走最后一个else，因为是second先比较，如果又出现第二对不匹配时，不会走第一个if和else
                            因为在第一次时就已经修改了f和s，所以，如果找到了两对不匹配，直接返回false
                        */
                        return false;
                }
            }

            // 按照上述算法比较
            return (second != -1 && A.charAt(first) == B.charAt(second) &&
                    A.charAt(second) == B.charAt(first));
        }
    }
}
